#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: title19.py 
@version:
@time: 2023/05/14 
https://leetcode.cn/problems/permutation-ii-lcci/
"""
import itertools
from typing import List


class Solution:
    def permutation(self, S: str) -> List[str]:
        return ["".join(e) for e in set(itertools.permutations(S))]


class Solution:
    def permutation(self, S: str) -> List[str]:
        n = len(S)
        if n == 0:
            return [""]
        res = []
        for i in range(n):
            if S[i] in S[:i]:  # 只需判断S[i]是否在S[:i]中出现过即可
                continue
            for s1 in self.permutation(S[:i] + S[i + 1:]):
                res.append(S[i] + s1)
        return res


assert Solution().permutation('ass') == ['ass', 'sas', 'ssa']
assert Solution().permutation('ab') == ['ab', 'ba']
print('测试通过')
